package main.leetcode.clockin.March;

import java.util.Arrays;

/**
 * 322.零钱兑换
 *
 * <p>给定不同面额的硬币 coins 和一个总金额 amount。编写一个函数来计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额，返回 -1。
 *
 * <p>示例 1: 输入: coins = [1, 2, 5], amount = 11 输出: 3 解释: 11 = 5 + 5 + 1
 *
 * <p>示例 2: 输入: coins = [2], amount = 3 输出: -1
 *
 * <p>说明: 你可以认为每种硬币的数量是无限的。
 *
 * <p>来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/coin-change
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class day8 {
    public static void main(String[] args) {
        System.out.println(new day8().coinChange(new int[] {186, 419, 83, 408}, 6249));
    }

    private int res = Integer.MAX_VALUE;

    // 回溯（dfs+剪枝）
    public int coinChange(int[] coins, int amount) {
        if (amount == 0) return 0;
        int n = coins.length;
        if (n == 0) return -1;
        Arrays.parallelSort(coins);
        dfs(coins, amount, n - 1, 0);
        return res == Integer.MAX_VALUE ? -1 : res;
    }

    private void dfs(int[] coins, int need, int index, int sum) {
        if (index < 0) return;
        for (int i = need / coins[index]; i >= 0; i--) {
            need -= coins[index] * i;
            sum += i;
            if (need == 0) { // 剪枝——分完了
                res = Math.min(res, sum);
                break;
            }
            if (sum + 1 > res) break; // 剪枝——超出记忆中的最小硬币个数
            dfs(coins, need, index - 1, sum);
            sum -= i; // 状态重置
            need += coins[index] * i;
        }
    }

    //  // 动态规划——自上而下
    //  public int coinChange(int[] coins, int amount) {
    //    if (amount == 0) return 0;
    //    if (coins.length == 0) return -1;
    //    return dp(coins, amount, new int[amount]);
    //  }
    //
    //  // int[] count 存储组成金额 i 所需的最少硬币数量
    //  private int dp(int[] coins, int need, int[] count) {
    //    if (need < 0) return -1;
    //    if (need == 0) return 0;
    //    if (count[need - 1] != 0) return count[need - 1];
    //    int res, min = Integer.MAX_VALUE;
    //    for (int coin : coins) { // 枚举最后一枚硬币的可能性
    //      res = dp(coins, need - coin, count);
    //      if (res >= 0 && res < min) min = res + 1;
    //    }
    //    count[need - 1] = min == Integer.MAX_VALUE ? -1 : min;
    //    return count[need - 1];
    //  }
    //
    //  // 动态规划——自下而上
    //  public int coinChange(int[] coins, int amount) {
    //    if (amount == 0) return 0;
    //    if (coins.length == 0) return -1;
    //    int[] dp = new int[amount + 1]; // 存储组成金额i所需最少的硬币数量
    //    Arrays.fill(dp, amount + 1); // 初始化成最大值
    //    dp[0] = 0;
    //    for (int i = 1; i <= amount; i++)
    //      for (int coin : coins)
    //        if (coin - i <= 0) // 最后一枚硬币的面值小于当前金额
    //        dp[i] = Math.min(dp[i], dp[i - coin] + 1); // F(i) = min F(i-cj) + 1
    //    return dp[amount] > amount ? -1 : dp[amount];
    //  }
}
